#ifndef __GEOCUTTABLESURFACE_H__
#define __GEOCUTTABLESURFACE_H__

#include "H3DNodeDatabase.h"
#include "X3DComposedGeometryNode.h"
#include "CoordBoundField.h"
#include "MFInt32.h"

namespace H3D
{
    class GeoCuttableSurface: public X3DComposedGeometryNode
    {
    public:

		/// Thrown if the number of colors in the color field is less than
		/// the number coordinates in the coord field.
		H3D_VALUE_EXCEPTION( int, NotEnoughColors );

		/// Thrown if the number of texture coordinates in the color field is less 
		/// than the number coordinates in the coord field.
		H3D_VALUE_EXCEPTION( int, NotEnoughTextureCoordinates );

        /// The bound field for IndexedFaceSet is a CoordBoundField.
        typedef CoordBoundField SFBound;

        /// Specialized field for automatically generating normals from
        /// coordinates.
        /// routes_in[0] is the normalPerVertex field.
        /// routes_in[1] is the coord field.
        /// routes_in[2] is the index field.
        /// routes_in[3] is the ccw field.

    class H3DAPI_API AutoNormal:
                    public TypedField< SFNormalNode,
                    Types< SFBool, SFCoordinateNode, MFInt32, SFBool > >
        {
            /// Calls generateNormalsPerVertex() if routes_in[0] is true,
            /// otherwise generateNormalsPerFace() is called.
            virtual void update();

            /// Create a new X3DNormalNode from the arguments given
            /// with one normal for each vertex specified.
            ///
            /// \param coord Node with the coordinates.
            /// \param index The indices in coord for the vertices.
            /// \param ccw Defines the ordering of the vertex coordinates of the
            /// geometry with respect to generated normal vectors used in the
            /// lighting model equations. If ccw is TRUE, the normals shall
            /// follow the right hand rule; the orientation of each normal with
            /// respect to the vertices (taken in order) shall be such that the
            /// vertices appear to be oriented in a counterclockwise order when
            /// the vertices are viewed (in the local coordinate system of the Shape)
            /// from the opposite direction as the normal.
            /// \returns A new Normal node with a normal for each
            /// vertex.
            ///
            virtual X3DNormalNode *generateNormalsPerVertex(
                X3DCoordinateNode *coord,
                const vector< int > &index,
                bool ccw );


            /// Create a new X3DNormalNode from the arguments given
            /// with one normal for each face specified.
            ///
            /// \param coord Node with the coordinates.
            /// \param index The indices in coord for the vertices.
            /// \param ccw Defines the ordering of the vertex coordinates of the
            /// geometry with respect to generated normal vectors used in the
            /// lighting model equations. If ccw is TRUE, the normals shall
            /// follow the right hand rule; the orientation of each normal with
            /// respect to the vertices (taken in order) shall be such that the
            /// vertices appear to be oriented in a counterclockwise order when
            /// the vertices are viewed (in the local coordinate system of the Shape)
            /// from the opposite direction as the normal.
            /// \returns A new Normal node with a normal for each
            /// vertex.
            ///
            virtual X3DNormalNode *generateNormalsPerFace(
                X3DCoordinateNode *coord,
                const vector< int > &index,
                bool ccw );

        };

        GeoCuttableSurface( Inst< SFNode           > _metadata        = 0,
                         Inst< SFBound          > _bound           = 0,
                         Inst< DisplayList      > _displayList     = 0,
                         Inst< SFColorNode      > _color           = 0,
                         Inst< SFCoordinateNode > _coord           = 0,
                         Inst< SFNormalNode     > _normal          = 0,
                         Inst< SFTextureCoordinateNode > _texCoord = 0,
                         Inst< SFBool           > _ccw             = 0,
                         Inst< SFBool           > _colorPerVertex  = 0,
                         Inst< SFBool           > _normalPerVertex = 0,
                         Inst< SFBool           > _solid           = 0,
                         Inst< MFVertexAttributeNode > _attrib     = 0,
						 Inst< AutoNormal       > _autoNormal      = 0,
                         Inst< MFInt32          > _set_index       = 0,
                         Inst< MFInt32          > _index           = 0,
					   	 Inst< SFBool			> _shouldCut	   = 0 );

        //virtual void Cut(GeoCuttableSurface *& sideOne, GeoCuttableSurface *& sideTwo);

        /// Traverse the scenegraph. A HLFeedbackShape is added for haptic
        /// rendering if haptics is enabled.
        virtual void traverseSG( TraverseInfo &ti );

        /// Renders the IndexedTriangleSet with OpenGL.
        virtual void render();

        /// Auto-generated normals that are used if the normal field is NULL.
        /// Only accessable in C++.
        ///autoNormal->setName( "autoNormal" );
        /// \dotfile IndexedFaceSet_autoNormal.dot
        auto_ptr< AutoNormal  >  autoNormal;

        /// Field for setting the value of the index field.
        /// <b>Access type:</b> inputOnly
        ///
        /// \dotfile IndexedTriangleSet_set_Index.dot
        auto_ptr< MFInt32 >  set_index;

        /// The index field is used to specify the vertices of each triangle
        /// from the coord field. Each triangle is formed from a set of three
        /// vertices of the Coordinate node identified by three consecutive
        /// indices from the index field. If the index field does not contain
        /// a multiple of three coordinate values, the remaining vertices shall
        ///be ignored.
        ///
        /// <b>Access type:</b> inputOnly
        ///
        /// \dotfile IndexedTriangleSet_index.dot
        auto_ptr< MFInt32 >  index;

		auto_ptr< SFBool > shouldCut;

        static H3DNodeDatabase database;

		private:
			void AppendPoint(vector<int>& indices,
							 vector<int *>& currentIndices,
							 const vector<Vec3f>& points,
							 vector<Vec3f>& newPoints,
							 int index, int offset);

			Vec3f _lastPosition;
			bool _wasCutting;
			bool _wasPressed;
			int _lastFace;
			
		public:
			// Lets us implement more sophisticated cutting algorithms
			class ShapeDatabase
			{
			public:

				class Edge;
				class Face;

				class Point
				{
				public:
					Point()
					{
						deleting = false;
						index = -1;
						pId = 0;
					};

					vector<Edge *> edges;
					vector<Face *> faces;
					bool deleting;
					int index;
					int pId;

					Face * getFaceLink(int index);
					int numFaceLinks();
					void ColorMeshForSplitAtNode(GeoCuttableSurface::ShapeDatabase::Point* other_node, ShapeDatabase & db, vector<Vec3f> & coords);
					Point * SplitColoredMeshAtNode(GeoCuttableSurface::ShapeDatabase::Point* other_node, ShapeDatabase & db, vector<Vec3f> & coords);

					void setPartId(int partId){this->pId = partId;}
					int getPartId(){return this->pId;}
				};

				class Edge
				{
				public:
					Edge()
					{
						faces[0] = faces[1] = NULL;
						endpoints[0] = endpoints[1] = NULL;
						deleting = false;
					};

					bool IsBorder()
					{
						if(faces[0] == NULL)
							return true;
						if(faces[1] == NULL)
							return true;

						return false;
					};

					Face * faces[2];
					Point * endpoints[2];
					bool deleting;
					//float lengthSq;
				};

				class Face
				{
				public:
					Face()
					{
						edges[0] = edges[1] = NULL;
						deleting = false;
					};

					Edge * edges[3];
					Point * points[3];
					bool deleting;
				};

				ShapeDatabase(GeoCuttableSurface * owner);
				~ShapeDatabase();

				Face * AddFace(Point * pt0, Point * pt1, Point * pt2);
				Edge * AddEdge(Point * pt0, Point * pt1);

				void DeleteFace(Face * faceIndex, bool deleteEdges = true);
				void DeleteEdge(Edge * edgeIndex);
				void DeletePoint(Point * pointIndex);
				vector<int> GetIndices();
				/*int GetClosestPoint(const Vec3f& pt);
				int GetClosestFace(const Vec3f& pt);
				bool IsOnFace(const Vec3f& pt, int face);*/

				float CalcLengthSquared(Point * pt0, Point * pt1);
				float CalcLengthSquared(const Vec3f & pt0, const Vec3f & pt1);

				void LogMesh();
				void Clear();

				static Point* subdivideFace(Face *initial_p,
											Vec3f S,
											ShapeDatabase & db,
											vector<Vec3f> & coords);

				static Point* subdivideFace(Face *initial_p,
											Point * node_S,
											ShapeDatabase & db,
											vector<Vec3f> & coords);

				// Functions needed:
				// Cut?
				// BisectFace
				// DeleteFace
				// DeleteEdge
				// DeletePoint
				// Decide if the preceding functions cascade up or not
				// It seems like they'll have to, unless you make it so
				// that something can't be deleted without its users being
				// deleted too

				set<Point *> points;
				set<Edge *> edges;
				set<Face *> faces;
				GeoCuttableSurface * _owner;

			private:
				//bool SameSide(const Vec3f & p0, const Vec3f & p1, const Vec3f & a, const Vec3f & b);

			};

			class DatabaseUpdater : public TypedField<SFBool, Types<SFCoordinateNode, MFInt32> >
			{
				virtual void update();
			public:
				ShapeDatabase * theDB;
			};

		private:
			DatabaseUpdater db;
			ShapeDatabase::Point * firstNode;
    };
}

#endif